//
//  myDecode.c
//  imageCompression
//
//  Created by cocoa on 16/5/6.
//  Copyright © 2016年 cocoa. All rights reserved.
//

#include "myDecode.h"
#include <stdio.h>

typedef unsigned char byte;

#define BITS 9

typedef struct {
    unsigned int table[1 << BITS];
    int tableCount;
    unsigned char *outBuff;
    int outSize;
    int CLEAR_CODE;
    int EOF_CODE;
    int crntBits;
    int lastCode;
    int mask;
} DecodeConfig;

static void output(unsigned char *outBuff, int outsz, unsigned char value);

static unsigned char outputCode(int code, DecodeConfig *config);

static void insertTable(int lastCode, unsigned char c, DecodeConfig *config);

static void inputCode(unsigned int *crntCode, int *inbyte, int *inbits, int crntBits, const byte *inBuff, int *inIndex);

int decodeBuff(const unsigned char *buf, int bufSize, unsigned char *outBuff, int *outSize, int colorCount) {
    
    DecodeConfig config;
    config.tableCount = 0;
    config.outBuff = outBuff;
    config.outSize = 0;
    
    colorCount -- ;
    int bits = 0;
    while (colorCount > 0) {
        bits ++ ;
        colorCount >>= 1;
    }
    if (bits < 2) {
        bits = 2;
    }
    config.CLEAR_CODE = 1 << bits; //rootMax
    config.EOF_CODE = config.CLEAR_CODE + 1;
    config.crntBits = bits + 1;
    config.lastCode = -1;
    config.mask = (1 << BITS) - 1;

    int inbyte = 0;
    int inbits = 0;
    int inIndex = 0;
    while (inIndex < bufSize) {
        unsigned int crntCode;
        inputCode(&crntCode, &inbyte, &inbits, config.crntBits, buf, &inIndex);
        printf("inputCode ==%i\n", crntCode);
        if (crntCode == config.CLEAR_CODE) {
            config.tableCount = 0;
            config.crntBits = bits + 1;
            config.lastCode = -1;
            continue;
        }
        if (crntCode == config.EOF_CODE) {
            break;
        }
        do {
            if (config.lastCode < 0) {
                output(config.outBuff, config.outSize ++ , crntCode);
                break;
            }
            //找到
            if (crntCode < config.tableCount + config.EOF_CODE + 1) {
                unsigned char c = outputCode(crntCode, &config);
                insertTable(config.lastCode, c, &config);
                break;
            }
            //没找到
            unsigned char c = outputCode(config.lastCode, &config);
            output(config.outBuff, config.outSize ++ , c);
            insertTable(config.lastCode, c, &config);
        } while (0);
        config.lastCode = crntCode;
    }
    *outSize = config.outSize;
    return 0;
}

static void output(unsigned char *outBuff, int outsz, unsigned char value) {
    outBuff[outsz] = value;
//    printf("%i, %i\n", outsz, value);
}

static unsigned char outputCode(int code, DecodeConfig *config) {
    if (code < config->CLEAR_CODE) {
        output(config->outBuff, config->outSize ++ , code);
        return code;
    }
    int codeInTable = code - config->EOF_CODE - 1;
    int ddcode = config->table[codeInTable];
    int l = (ddcode >> (BITS + 8));
    for (int i = l; i > 0; --i) {
        output(config->outBuff, config->outSize + i, ddcode & 0xff);
        ddcode = (ddcode >> 8) & config->mask;
        if (i > 1) {
            ddcode = config->table[ddcode - config->EOF_CODE - 1];
        }
    }
    output(config->outBuff, config->outSize, ddcode & 0xff);
    config->outSize += l + 1;
    return ddcode & 0xff;
}

static void insertTable(int lastCode, unsigned char c, DecodeConfig *config) {
    int l = lastCode < config->CLEAR_CODE ? 1 : ((config->table[lastCode - config->EOF_CODE - 1] >> (BITS + 8)) + 1);
    config->table[config->tableCount ++ ] = (l << (BITS + 8)) | (lastCode << 8) | c;
    if (config->tableCount + config->EOF_CODE >= (1 << config->crntBits) - 1 && config->crntBits < BITS) {
        config->crntBits ++ ;
    }
    static int xx = 0;
    printf("%i, table == l=%i, %i, %i, %i\n", xx++, l, config->tableCount - 1 + 6, config->lastCode, c);
}

static void inputCode(unsigned int *crntCode, int *inbyte, int *inbits, int crntBits, const byte *inBuff, int *inIndex) {
    static const unsigned short CodeMasks[] = {
        0x0000, 0x0001, 0x0003, 0x0007,
        0x000f, 0x001f, 0x003f, 0x007f,
        0x00ff, 0x01ff, 0x03ff, 0x07ff,
        0x0fff
    };
    byte NextByte;
    while (*inbits < crntBits) {
        /* Needs to get more bytes from input stream for next code: */
        NextByte = inBuff[(*inIndex)++];
        *inbyte |= NextByte << *inbits;
        *inbits += 8;
    }
    *crntCode = *inbyte & CodeMasks[crntBits];
    
    *inbyte >>= crntBits;
    *inbits -= crntBits;
}

